import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class QuickSums {
	public int minSums(String numbers, int sum) {
		int N = numbers.length();
		long[][] dp = new long[N][sum + 1];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j <= sum; j++) {
				dp[i][j] = Long.MAX_VALUE - 1;
			}
		}
		for (int i = 0; i < N; i++) {
			long tmp = Long.parseLong(numbers.substring(0, i + 1));
			if (tmp <= sum)
				dp[i][(int) tmp] = 0;
			else
				break;
		}
		// for (int i = 0; i < N; i++) {
		// for (int j = 0; j <= sum; j++) {
		// System.out.print(dp[i][j]);
		// System.out.print(", ");
		// }
		// System.out.println();
		// }
		// System.out.println();
		for (int i = 0; i < N; i++) {
			for (int k = 1; k <= i; k++) {
				long tmp = Long.parseLong(numbers.substring(k, i + 1));
				if (tmp > sum)
					continue;
				for (int j = 0; j <= sum; j++) {
					if (j >= tmp)
						dp[i][j] = Math.min(dp[i][j],
								dp[k - 1][j - (int) tmp] + 1);
				}
			}
		}
		// for (int i = 0; i < N; i++) {
		// for (int j = 0; j <= sum; j++) {
		// System.out.print(dp[i][j]);
		// System.out.print(", ");
		// }
		// System.out.println();
		// }
		if (dp[N - 1][sum] == Long.MAX_VALUE - 1)
			return -1;
		return (int) dp[N - 1][sum];
	}
	 public static void main(String[] args)
	{
		long time;
		int answer;
		boolean errors = false;
		int desiredAnswer;
		
		
		time = System.currentTimeMillis();
		answer = new QuickSums().minSums("99999", 45);
		System.out.println("Time: " + (System.currentTimeMillis()-time)/1000.0 + " seconds");
		desiredAnswer = 4;
		System.out.println("Your answer:");
		System.out.println("\t" + answer);
		System.out.println("Desired answer:");
		System.out.println("\t" + desiredAnswer);
		if (answer != desiredAnswer)
		{
			errors = true;
			System.out.println("DOESN'T MATCH!!!!");
		}
		else
			System.out.println("Match :-)");
		System.out.println();
		time = System.currentTimeMillis();
		answer = new QuickSums().minSums("1110", 3);
		System.out.println("Time: " + (System.currentTimeMillis()-time)/1000.0 + " seconds");
		desiredAnswer = 3;
		System.out.println("Your answer:");
		System.out.println("\t" + answer);
		System.out.println("Desired answer:");
		System.out.println("\t" + desiredAnswer);
		if (answer != desiredAnswer)
		{
			errors = true;
			System.out.println("DOESN'T MATCH!!!!");
		}
		else
			System.out.println("Match :-)");
		System.out.println();
		time = System.currentTimeMillis();
		answer = new QuickSums().minSums("0123456789", 45);
		System.out.println("Time: " + (System.currentTimeMillis()-time)/1000.0 + " seconds");
		desiredAnswer = 8;
		System.out.println("Your answer:");
		System.out.println("\t" + answer);
		System.out.println("Desired answer:");
		System.out.println("\t" + desiredAnswer);
		if (answer != desiredAnswer)
		{
			errors = true;
			System.out.println("DOESN'T MATCH!!!!");
		}
		else
			System.out.println("Match :-)");
		System.out.println();
		time = System.currentTimeMillis();
		answer = new QuickSums().minSums("99999", 100);
		System.out.println("Time: " + (System.currentTimeMillis()-time)/1000.0 + " seconds");
		desiredAnswer = -1;
		System.out.println("Your answer:");
		System.out.println("\t" + answer);
		System.out.println("Desired answer:");
		System.out.println("\t" + desiredAnswer);
		if (answer != desiredAnswer)
		{
			errors = true;
			System.out.println("DOESN'T MATCH!!!!");
		}
		else
			System.out.println("Match :-)");
		System.out.println();
		time = System.currentTimeMillis();
		answer = new QuickSums().minSums("382834", 100);
		System.out.println("Time: " + (System.currentTimeMillis()-time)/1000.0 + " seconds");
		desiredAnswer = 2;
		System.out.println("Your answer:");
		System.out.println("\t" + answer);
		System.out.println("Desired answer:");
		System.out.println("\t" + desiredAnswer);
		if (answer != desiredAnswer)
		{
			errors = true;
			System.out.println("DOESN'T MATCH!!!!");
		}
		else
			System.out.println("Match :-)");
		System.out.println();
		time = System.currentTimeMillis();
		answer = new QuickSums().minSums("9230560001", 71);
		System.out.println("Time: " + (System.currentTimeMillis()-time)/1000.0 + " seconds");
		desiredAnswer = 4;
		System.out.println("Your answer:");
		System.out.println("\t" + answer);
		System.out.println("Desired answer:");
		System.out.println("\t" + desiredAnswer);
		if (answer != desiredAnswer)
		{
			errors = true;
			System.out.println("DOESN'T MATCH!!!!");
		}
		else
			System.out.println("Match :-)");
		System.out.println();
		
		
		if (errors)
			System.out.println("Some of the test cases had errors :-(");
		else
			System.out.println("You're a stud (at least on the test data)! :-D ");
	}

}
// Powered by [KawigiEdit] 2.0!
